package 剑指offer_leetcode;

import java.util.ArrayList;

/**
 * JZ41数据流中的中位数
 */
public class 剑指Offer41_数据流中的中位数 {
    class MedianFinder {
        ArrayList<Integer> value ;
        /** initialize your data structure here. */
        public MedianFinder() {
            this.value = new ArrayList<>();
        }

        public void addNum(int num) {
            if(value.size()==0)
                value.add(num);
            else{
                int i=0;
                for(;i<value.size();i++){
                    if(value.get(i)<num){
                        break;
                    }
                }
                value.add(i,num);
            }
        }

        public double findMedian() {
            if(value.size()%2==1)
                return (double)(value.get(value.size()/2));
            else{
                return (value.get(value.size()/2) + value.get(value.size()/2 - 1)) / 2.0;
            }
        }
    }
}
